package Sort;

/**
 * @Author: ylc
 * @Description:
 * @Date Created in 2022-04-21 19:38
 */
public class Sort {
    /**
     * 冒泡排序
     * @param array
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {    //外层循环控制比较的轮数
            for (int j = 0; j < array.length - i - 1; j++) {    //内层循环控制每一轮比较的次数
                if (array[j] > array[j + 1]) {  //相等则不交换。保证其稳定性
                    swap(array, j, j + 1);
                }
            }
        }
    }

    /**
     * 快速排序
     * @param array
     */
    public static void quickSort(int[] array) {
        quickSortInternal(array, 0, array.length - 1);
    }

    private static void quickSortInternal(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        //pivotIndex作为基准值最终下标
        int pivotIndex = partition(array, left, right);

        //[left,pivotIndex - 1]小于基准值区间
        //[pivotIndex + 1, right]大于基准值区间
        quickSortInternal(array, left, pivotIndex - 1);
        quickSortInternal(array, pivotIndex + 1, right);
    }

    //该块作用是遍历整个待排序区间，小于基准值的放到基准值的左边，大于基准值的放到基准值的右边。
    private static int partition(int[] array, int left, int right) {
        int i = left;
        int j = right;
        int pivot = array[left];//选择基准值最简单的方式，选择array[left]作为基准值

        while (i < j) {
            //从右往左找到小于pivot的下标
            while (i < j && array[j] >= pivot) {
                j--;
            }
            //从左往右找到大于pivot的下标
            while (i < j && array[i] <= pivot) {
                i++;
            }
            //上述循环找到了符合条件的 i, j 后交换两数
            swap(array, i, j);
        }
        //将基准值移到中间
        swap(array, i, left);
        return i;
    }

    /**
     * 选择排序
     * @param array
     */
    public static void selectSort(int[] array) {
        //[0,array.length - i]无序区间
        //[array.length - i, array.length]有序区间

        for (int i = 0; i < array.length; i++) {//将最后一位作为初始有序区间
            int max = 0;
            for (int j = 0; j < array.length - i; j++) {//选择无序区间中最大的值
                if (array[j] > array[max]) {
                    max = j;
                }
            }
            //将选择出的最大值置换到有序区间
            swap(array, array.length - i - 1, max);
        }
    }

    /**
     * 双向选择排序
     * @param array
     */
    public static void selectSortOP(int[] array) {
        int low = 0;
        int high = array.length - 1;
        // low = high，无序区间只剩下一个元素，整个数组已经有序
        while (low <= high) {
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (array[i] < array[min]) {
                    min = i;
                }
                if (array[i] > array[max]) {
                    max = i;
                }
            }
            // min索引一定是当前无序区间的最小值索引，与low交换位置
            swap(array, low, min);
            if (max == low) {
                // 最大值已经被换到min这个位置
                max = min;
            }
            swap(array, high, max);
            low++;
            high--;
        }

    }

    /**
     * 直接插入排序
     * @param array
     */
    public static void insertSort(int[] array) {
        // 有序区间: [0, i)
        // 无序区间: [i, array.length)
        for (int i = 1; i < array.length; i++) {
            int val = array[i];//无序区间第一个数
            int j = i - 1; //不使用j = val是为了保证排序的稳定性
            for (; j >= 0 && array[j] > val; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = val;
        }
        /*for (int i = 1; i < array.length; i++) {
            // 无序区间第一个元素array[i]
            // 从待排序区间的第一个元素向前看，找到合适的插入位置
            for(int j = i - 1; j >= 0 && array[j + 1] < array[j]; j--){
                swap(array, j, j + 1);
            }
        }*/
    }

    /**
     * 折半插入排序
     * @param array
     */
    public static void insertSortBS(int[] array) {
        // 有序区间[0..i)
        // 无序区间[i...n]
        for (int i = 1; i < array.length; i++) {
            int val = array[i];
            int left = 0;
            int right = i;
            while (left < right) {
                // int mid = left + ((right - left) >> 1);
                //当left，right的值很大，(left + right)有可能会溢出
                int mid = (left + right) >> 1;
                if (val < array[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            // 搬移left..i的元素
            for (int j = i; j > left; j--) {
                array[j] = array[j - 1];
            }
            // left就是val插入的位置
            array[left] = val;
        }
    }

    /**
     * 希尔排序
     * @param array
     */
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            insertSortGap(array,gap);
            gap = gap / 2;
        }
        insertSortGap(array, 1);
    }
    private static void insertSortGap(int[] array, int gap){
        // 有序区间: [0, i)
        // 无序区间: [i, array.length)
        for(int i = 1; i < array.length; i++){
            int v = array[i];//无序区间第一个数
            int j = i - gap; //不使用j = v是为了保证排序的稳定性
            for(; j >= 0 && array[j] > v; j -= gap){
                array[j+gap] = array[j];
            }
            array[j+gap] = v;
        }
    }

    /**
     * 堆排序
     * @param array
     */
    public static void heapSort(int[] array) {
        createHeap(array);  //构建一个大顶堆，保证数组第一个元素时最大的

        for(int i = 0; i < array.length - 1; i++){
            //交换0号元素与无序区间的最后一个元素
            swap(array,0, array.length - i - 1);
            //在交换后，数组末尾元素则为最大值，再一次遍历时应排除该元素，对无序区间重新构建一个大顶堆
            maxHeap(array,array.length - i - 1,0);
        }

    }
    private static void createHeap(int[] array) {
        for(int i = (array.length - 1) / 2; i >= 0; i--){
            maxHeap(array, array.length, i);
        }
    }
    private static void maxHeap(int[] array, int heapSize, int index) {
        //二叉树的下标关系
        int left = 2 * index + 1;      //左孩子
        int right = 2 * index + 2;      //右孩子
        int max = index;

        //比较左子节点的值，如果比当前左节点的值大，则把最大值的位置换成左子节点的位置
        if(left < heapSize && array[left] > array[max]){
            max = left;
        }
        if(right < heapSize && array[right] > array[max]){
            max = right;
        }
        //如果不相等则说明其子节点存在更大的数值，则位置发生交换
        if(max != index){
            swap(array,index,max);
            // 交换完位置后还需要判断子节点是否打破了最大堆的性质。最大堆性质：两个子节点都比父节点小。
            maxHeap(array, heapSize, max);
        }

    }


    /**
     * 归并排序
     * @param array
     */
    public static void mergeSort(int[] array) {
        mergeSortInternal(array, 0, array.length - 1);
    }
    // 待排序区间为 [low, high)
    private static void mergeSortInternal(int[] array, int L, int R) {
        if (L - 1 >= R) {
            return;
        }

        int mid = L + ((R - L) >> 1);

        mergeSortInternal(array, L, mid);
        mergeSortInternal(array, mid + 1, R);
        merge(array, L, mid, R);
    }
    private static void merge(int[] array, int L, int mid, int R) {
        int i = L;
        int j = mid + 1;
        int[] extra = new int[R - L + 1];
        int k = 0;

        // 选择小的放入 extra
        while (i <= mid && j <= R) {
            // 加入等于，保证稳定性
            extra[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }

        // 将左边剩余元素放入 extra
        while (i <= mid) {
            extra[k++] = array[i++];
        }
        // 将右边剩余元素放入 extra
        while (j <= R) {
            extra[k++] = array[j++];
        }

        // 从 extra 搬移回 array
        for (int t = 0; t < extra.length; t++) {
            // 需要搬移回原位置，从 L 开始
            array[L + t] = extra[t];
        }
    }
    private static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

}
